package de.pass.ch.graph;

import static de.pass.ch.util.Constants.*;

import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.io.Serializable;
import java.util.Comparator;

import de.pass.ch.datastr.EdgeList;
import de.pass.ch.graph.edge.CompleteEdge;
import de.pass.ch.graph.edge.Edge;
import de.pass.ch.graph.node.UpNode;

public class UpdateableGraph implements IGraph, Serializable {

	private static final long serialVersionUID = 6501143315171606652L;

	private UpNode[] nodes;
	private int noOfEdges;

	public UpdateableGraph(int noOfNodes) {
		nodes = new UpNode[noOfNodes];
		noOfEdges = 0;
	}

	/** Constructor. Builds the graph. */
	public UpdateableGraph(EdgeList edges, int[] nodeLevels) {
		this(nodeLevels.length);
		construct(edges, nodeLevels);
	}

	@Override
	public UpNode node(int nodeID) {
		assert (nodeID < nodes.length) : "nodeID must be smaller than nodes.size()!";
		return nodes[nodeID];
	}

	@Override
	public Edge edge(int nodeID, int edgeID) {
		return nodes[nodeID].edge(edgeID);
	}

	@Override
	public int noOfNodes() {
		return nodes.length;
	}

	@Override
	public int noOfEdges() {
		return noOfEdges;
	}

	/**
	 * Returns the index of the first edge of nodeID that leads to the same or
	 * higher level.
	 */
	@Override
	public int firstLevelEdge(int nodeID) {
		return node(nodeID).getFirstLevelEdge();
	}

	/** Returns the index+1 of the last edge of nodeID. */
	@Override
	public int lastEdge(int nodeID) {
		return node(nodeID).lastEdge();
	}

	/** Sort edges. */
	public void sortEdges(int nodeID) {
		nodes[nodeID].sortEdges();
	}

	/**
	 * The adjacency array of a node is partitioned into the edges leading to
	 * lower levels and the edges leading to the same or higher levels. This
	 * method ensures this partition if only the specified edge may violate it.
	 */
	public void changeEdgeLevel(int nodeID, int edgeID) {
		assert ((0 <= edgeID) && (edgeID < lastEdge(nodeID)));

		// edge e leads to a lower level and is in the wrong partiton
		if (node(nodeID).getLevel() > node(edge(nodeID, edgeID).getTarget())
				.getLevel() && edgeID >= firstLevelEdge(nodeID)) {
			if (edgeID > firstLevelEdge(nodeID)) {
				swapEdges(nodeID, edgeID, firstLevelEdge(nodeID));
			}
			node(nodeID).setFirstLevelEdge(firstLevelEdge(nodeID) + 1);
		}

		// edge e leads to the same or higher level and is in the wrong partiton
		else if (node(nodeID).getLevel() <= node(
				edge(nodeID, edgeID).getTarget()).getLevel()
				&& edgeID < firstLevelEdge(nodeID)) {
			if (edgeID < firstLevelEdge(nodeID) - 1) {
				swapEdges(nodeID, edgeID, firstLevelEdge(nodeID) - 1);
			}
			node(nodeID).setFirstLevelEdge(firstLevelEdge(nodeID) - 1);
		}
	}

	/**
	 * The adjacency array of a node is partitioned into the edges leading to
	 * lower levels and the edges leading to the same or higher levels. This
	 * method is called after the level of node u changed. It ensures the
	 * correct partition of the edges if only the edges leading to more
	 * important nodes incident to node u may violate it and the partition is
	 * correct for the adjacency array of node u. So only the reverse edges
	 * between firstLevelEdge .. lastEdge-1 need to be checked. This special
	 * case occurs during node contraction. Not until after the contraction of a
	 * node, its level in the graph datastructure is updated. Then, inductive,
	 * its own adjacency array is partitioned correct but the adjacency array of
	 * its remaining neighbors need an update because from their point of view
	 * the edge now leads to a lower level.
	 */
	public void changeNodeLevelOnlyReverseEdges(int nodeID) {

		int lastEdge = lastEdge(nodeID);
		for (int e = firstLevelEdge(nodeID); e < lastEdge; e++) {
			Edge edge = edge(nodeID, e);

			changeEdgeLevel(edge.getTarget(), reverseLevelEdge(nodeID, e));
		}
	}

	/**
	 * Returns the ID of the edge (v,u) that corresponds to the specified edge
	 * (u,v). If there are several reverse edges, returns the one in the highest
	 * level.
	 */
	public int reverseLevelEdge(int nodeID, int edgeID) {

		assert (!edge(nodeID, edgeID).isClosed()) : "edgeID is closed!";

		int v = edge(nodeID, edgeID).getTarget();
		Edge orgEdge = edge(nodeID, edgeID);
		// if there are several reverse edges, take the one in the highest level
		// therefore: for-loop runs backwards
		for (int f = lastEdge(v) - 1; f >= firstLevelEdge(v); f--) {
			Edge edge = edge(v, f);

			if (edge.isReverse(nodeID, orgEdge))
				return f;
			if (f == 0)
				break;
		}

		assert (false) : "ERROR at reverseLevelEdge!";

		return 0;
	}

	/**
	 * Removes the specified edge (u,v) with ID e. Leaves a new hole in the data
	 * structure. If the capacity was 2^[k+1} and the size is now reduced from
	 * 2^k + 1 to 2^k, we mark that the node u has an increased capacity of
	 * 2^[k+1}. WARNING: Using only one bit to mark an increased capacity, we
	 * cannot mark the case that the size is reduced to 2^{k-1} (or even less),
	 * although there is space for 2^[k+1} edges.
	 */
	public void removeEdge(int nodeID, int edgeIndex) {
		node(nodeID).removeEdge(edgeIndex);
		noOfEdges--;

		if (edgeIndex < firstLevelEdge(nodeID)) {
			node(nodeID).setFirstLevelEdge(firstLevelEdge(nodeID) - 1);
		}
		node(nodeID).setLastEdge(lastEdge(nodeID) - 1);
	}

	/**
	 * Add a shortcut edge at source and target and keeps invariant invariant:
	 * for each pair of nodes (u,v) there is at most one edge (u,v) Always the
	 * shortest edge is kept. This method is used during the construction of a
	 * contraction hierarchy to add shortcut edges that represent existing paths
	 * in the graph.
	 * 
	 * @return edge difference
	 */
	public int addShortcutEdge(int u, Edge newEdge) {
		return doAddShortcutEdge(u, newEdge, false);
	}

	/**
	 * Same as addShortcutEdge, but only simulate the operation to calculate the
	 * edge difference. This is used during node ordering as priority.
	 */
	public int addShortcutEdgeSimulate(int u, Edge newEdge) {
		return doAddShortcutEdge(u, newEdge, true);
	}

	/**
	 * Returns true iff for any edge (u,v), the graph also contains a
	 * corresponding edge (v,u).
	 */
	public boolean checkReverseGraphExists() {
		System.out.println("------   checkReverseGraphExists   ------");
		for (int nodeID = 0; nodeID < noOfNodes(); nodeID++) {
			for (int e = 0; e < lastEdge(nodeID); e++) {
				// if this method fails, the program terminates with an error
				// message
				reverseEdge(nodeID, edge(nodeID, e));
			}
		}
		return true;
	}

	public void deleteNode(int i) {
		nodes[i] = null;
	}

	public int[] getLevelInformation() {

		int[] levels = new int[nodes.length];
		UpNode node = null;
		int level = 0;

		for (int i = 0; i < nodes.length; i++) {
			node = node(i);
			level = node.getLevel();

			assert (level >= 0 && level < levels.length) : "ungueltiges Level";

			levels[level] = i;
		}

		return levels;
	}

	public void serialize(OutputStream out) {

		long start = System.currentTimeMillis();

		ObjectOutputStream oOut = null;

		try {

			oOut = new ObjectOutputStream(out);
			oOut.writeObject(this);

		} catch (IOException e) {
			e.printStackTrace();
			oOut = null;
		} finally {
			try {
				oOut.close();
			} catch (Exception e2) {
				oOut = null;
			}
		}

		System.out.println("\nSerializing of UpdateableGraph took "
				+ (System.currentTimeMillis() - start) + " ms");

	}

	public static UpdateableGraph deserialize(InputStream in) {

		long start = System.currentTimeMillis();

		ObjectInputStream oIn = null;
		UpdateableGraph res = null;

		try {

			oIn = new ObjectInputStream(in);
			res = (UpdateableGraph) oIn.readObject();

			oIn.close();

		} catch (IOException e) {
			e.printStackTrace();
			oIn = null;
		} catch (ClassNotFoundException e) {
			e.printStackTrace();
		} finally {
			try {
				oIn.close();
			} catch (Exception e2) {
				oIn = null;
			}
		}

		System.out.println("\nDeserializing of UpdateableGraph took "
				+ (System.currentTimeMillis() - start) + " ms");

		return res;

	}

	protected void deleteEdge(int i, int e) {
		nodes[i].deleteEdge(e);
	}

	private void swapEdges(int node, int edge1, int edge2) {
		node(node).swap(edge1, edge2);
	}

	/**
	 * Returns the ID of the edge (v,u) that corresponds to the given edge
	 * (u,v).
	 */
	private int reverseEdge(int u, Edge e) {
		int target = e.getTarget();
		int last = lastEdge(target);
		for (int f = 0; f < last; f++) {
			Edge edge = edge(target, f);
			if (edge.isReverse(u, e))
				return f;
		}

		assert (false) : "ERROR at reverseEdge! node: " + u;

		return 0;
	}

	private int doAddShortcutEdge(int node, Edge newEdge, boolean simulate) {
		// Flags indicating the directions for that we need a new edge.
		// If we found an existing edge with <= weight or we can used
		// the position of an existing edge, we unset these variables
		// accordingly.
		boolean forward = true;
		boolean backward = newEdge.isBidirected();

		// Current state of the search for a parallel edge. NOTHING = no edge
		// found ONE_EDGE = one unidirectional edge found TWO_EDGES = two
		// unidirectional or one bidirectional edge found
		// LOOK_FOR_SECOND_EDGE_FORWARD = old edge is unidirectional backward,
		// new edge is bidirectional. Need to check wheter a second
		// unidirectional forward edge exists. LOOK_FOR_SECOND_EDGE_BACKWARD =
		// old edge is unidirectional forward, new edge is bidirectional. Need
		// to check wheter a second unidirectional backward edge exists.
		int state = NOTHING;

		// If we replaced an existing unidirectional edge by a bidirectional
		// edge (state LOOK_FOR_SECOND_EDGE_FORWARD or
		// LOOK_FOR_SECOND_EDGE_BACKWARD) we need to look for a possible second
		// edge. If we found such an edge, and this edge is shorter than our new
		// edge, we need to make our new bidirectional edge one-way. These to
		// variables store the indices to these edges to perform makeOneWay().
		int changedEdgeID = SPECIAL_NODEID;
		int changedReverseEdgeID = SPECIAL_NODEID;

		// Only allow shortcut edges between nodes in the same level
		assert (node(node).getLevel() == node(newEdge.getTarget()).getLevel()) : "level(nodel): "
				+ node(node).getLevel()
				+ "  level(target): "
				+ node(newEdge.getTarget()).getLevel() + "  edge: " + newEdge;
		int edgeID = firstLevelEdge(node);
		int lastEdge = lastEdge(node);

		int result = 0;

		// Scan through the adjacency array of
		for (; edgeID < lastEdge && (forward || backward) && state < TWO_EDGES; edgeID++) {
			Edge edge = edge(node, edgeID);

			assert (!edge.isClosed());
			if (edge.getTarget() == newEdge.getTarget()) {
				// Found a matching edge.
				state++;
				if (edge.isBidirected())
					state++;
				assert (state <= TWO_EDGES);

				// Existing edge with <= weight can be used, shortcut not
				// necessary.
				if (edge.getWeight() <= newEdge.getWeight()) {
					forward = forward && !edge.isDirected((byte) 0);
					backward = backward && !edge.isDirected((byte) 1);
				}

				// new edge has smaller weight
				else {
					if (edge.isBidirected()) {
						int reverseEdgeID = reverseLevelEdge(node, edgeID);
						Edge reverseEdge = edge(edge.getTarget(), reverseEdgeID);
						if (forward && backward) {
							// old and new edge bidirectional
							if (!simulate) {
								edge.setWeight(newEdge.getWeight());
								reverseEdge.setWeight(newEdge.getWeight());
								if (edge.getType() != newEdge.getType()) {
									edge.setType(newEdge.getType());
									reverseEdge.setType(newEdge.getType());
								}
								edge.copyShortcutInfo(newEdge, false);
								reverseEdge.copyShortcutInfo(newEdge, true);
							}

							// replace old edge by new edge
							forward = false;
							backward = false;
						} else if (forward) {
							// old edge bidirectional, new edge only forward
							// => old edge becomes backward
							if (!simulate) {
								edge.makeOneWay((byte) 1);
								reverseEdge.makeOneWay((byte) 0);
							}
						} else if (backward) {
							// old edge bidirectional, new edge only backward
							// => old edge becomes forward
							if (!simulate) {
								edge.makeOneWay((byte) 0);
								reverseEdge.makeOneWay((byte) 1);
							}
						}
					}

					// old edge unidirectional
					else {
						if ((edge.isDirected((byte) 0) && forward)
								|| (edge.isDirected((byte) 1) && backward)) {
							// new edge covers all directions that the old edge
							// covers
							int reverseEdgeID = reverseLevelEdge(node, edgeID);
							Edge reverseEdge = edge(edge.getTarget(),
									reverseEdgeID);

							if (!simulate) {
								edge.setWeight(newEdge.getWeight());
								reverseEdge.setWeight(newEdge.getWeight());
								if (edge.getType() != newEdge.getType()) {
									edge.setType(newEdge.getType());
									reverseEdge.setType(newEdge.getType());
								}
								edge.copyShortcutInfo(newEdge, false);
								reverseEdge.copyShortcutInfo(newEdge, true);
							}

							if (forward && backward) {
								// old edge is not bidirectional, new edge is
								// bidirectional
								if (state == ONE_EDGE) {
									// There could be another old edge in the
									// opposite
									// direction. We need to look for it.
									state = edge.isDirected((byte) 0) ? LOOK_FOR_SECOND_EDGE_BACKWARD
											: LOOK_FOR_SECOND_EDGE_FORWARD;
									changedEdgeID = edgeID;
									changedReverseEdgeID = reverseEdgeID;
								}
								if (!simulate) {
									edge.makeTwoWay();
									reverseEdge.makeTwoWay();
								}
							}

							// replace old edge by new edge, no need to add a
							// new edge
							forward = false;
							backward = false;
						}
					}
				}
			}
		}

		// If a unidirectional edge was replaced by a bidirectional one
		// check for unidirectional edge in other direction.
		if (state == LOOK_FOR_SECOND_EDGE_FORWARD
				|| state == LOOK_FOR_SECOND_EDGE_BACKWARD) {
			for (; edgeID < lastEdge; edgeID++) {
				Edge edge = edge(node, edgeID);

				assert (!edge.isClosed());
				if (edge.getTarget() == newEdge.getTarget()) {
					assert (state != LOOK_FOR_SECOND_EDGE_FORWARD || (edge
							.isDirected((byte) 0) && !edge.isDirected((byte) 1)));
					assert (state != LOOK_FOR_SECOND_EDGE_BACKWARD || (edge
							.isDirected((byte) 1) && !edge.isDirected((byte) 0)));

					// this one is shorter than our new edge, reduce our edge to
					// one-way (unidirectional)
					if (edge.getWeight() < newEdge.getWeight()) {
						if (!simulate) {
							Edge changedEdge = edge(node, changedEdgeID);
							Edge changedReverseEdge = edge(edge.getTarget(),
									changedReverseEdgeID);
							if (state == LOOK_FOR_SECOND_EDGE_FORWARD) {
								// changed edge only backwards
								changedEdge.makeOneWay((byte) 1);
								changedReverseEdge.makeOneWay((byte) 0);
							} else {
								// changed edge only forwards
								changedEdge.makeOneWay((byte) 0);
								changedReverseEdge.makeOneWay((byte) 1);
							}
						}
					}
					// our new edge covers this one, remove it
					else {
						if (!simulate) {
							int reverseEdgeID = reverseEdge(node, edge);
							removeEdge(node, edgeID);
							removeEdge(newEdge.getTarget(), reverseEdgeID);
						}
						result -= 2;
					}
					break;
				}
			}
		}

		// A new edge is necessary because there were no usable existing edges
		// with
		// same source and target.
		if (forward || backward) {
			if (!simulate) {
				Edge edgeFw = new Edge(newEdge.getTarget(),
						newEdge.getWeight(), newEdge.getType(), forward,
						backward, newEdge.getShortcutMiddle(),
						newEdge.getShortcutEdge1(), newEdge.getShortcutEdge2(),
						newEdge.getShortcutOriginalEdgeCount());
				addEdge(node, edgeFw);
				addEdge(newEdge.getTarget(), new Edge(node, edgeFw));
			}
			result += 2;
		}

		return result;
	}

	/**
	 * Adds the given edge leaving node nodeID to the graph.
	 * 
	 * @return the number of places the edge group of nodeID is moved by this
	 *         operation; this is important when we have an id of an edge
	 *         (nodeID,v) before this operation is performed and want to use the
	 *         correct edge id after this operation has been performed.
	 */
	private int addEdge(int nodeID, Edge edge) {

		if (node(nodeID).getLevel() > node(edge.getTarget()).getLevel()) {

			node(nodeID).addEdge(edge, firstLevelEdge(nodeID));
			node(nodeID).setFirstLevelEdge(firstLevelEdge(nodeID) + 1);

		} else {

			node(nodeID).addEdge(edge);

		}
		noOfEdges++;

		return 1;
	}

	/**
	 * Initializes this UpdateableGraph from a given list of edges and node
	 * levels. Note that the overlay graph hierarchy is constructed later. Also
	 * the preprocessing of contraction hierarchies assumes that the remaining
	 * nodes (at the beginning all nodes) are in the same highest level.
	 */
	private void construct(EdgeList _edges, int[] nodeLevels) {
		assert (!(nodeLevels.length < 1)) : "nodeLevels empty!";

		// reserve RAM in advance
		// necessary because memory space will get fragmented
		// and large graphs like ORTEC need more than 2GB
		// _edges.reserve(5 << 26);

		for (int u = 0; u < nodeLevels.length; u++) {
			nodes[u] = new UpNode(nodeLevels[u]);
		}

		// re-arrange edges (sort)
		CompleteEdgeComparator comp = new CompleteEdgeComparator(this);
		long start = System.currentTimeMillis();
		_edges.sort(0, _edges.size(), comp);
		System.out.println("_edges.sort took "
				+ (System.currentTimeMillis() - start) + " ms");

		comp = null;

		// build adjacency array and indices
		// for each node into the adjacency array
		CompleteEdge edge = _edges.get(0);
		for (int u = 0; u < nodeLevels.length; u++) {

			UpNode nodeU = nodes[u];
			// nodeU.setFirstEdge(edges.size());

			while ((_edges.size() > 0) && (edge.getSource() == u)
					&& (node(edge.getTarget()).getLevel() < node(u).getLevel())) {
				assert (edge.getWeight() >= 0) : "weight should be >= 0 but was "
						+ edge.getWeight();
				nodeU.addEdge(edge.getEdge());
				noOfEdges++;
				if (!(_edges.size() > 1))
					break;
				edge = _edges.get(1);
				_edges.remove(0);
			}

			nodeU.setFirstLevelEdge(nodeU.lastEdge());

			while ((_edges.size() > 0) && (edge.getSource() == u)) {
				assert (edge.getWeight() >= 0) : "weight should be >= 0 but was "
						+ edge.getWeight();
				nodeU.addEdge(edge.getEdge());
				noOfEdges++;
				if (!(_edges.size() > 1))
					break;
				edge = _edges.get(1);
				_edges.remove(0);
			}

		}

		_edges = null;
		System.gc();

		assert (checkReverseGraphExists()) : "Reverse-Graph doesn't exist!";

	}

	private class CompleteEdgeComparator implements Comparator<CompleteEdge> {

		private UpdateableGraph graph;

		private CompleteEdgeComparator(UpdateableGraph graph) {
			this.graph = graph;
		}

		@Override
		public int compare(CompleteEdge ce1, CompleteEdge ce2) {
			if (ce1.getSource() == ce2.getSource()) {
				return graph.node(ce1.getTarget()).getLevel() < graph.node(
						ce2.getTarget()).getLevel() ? -1 : 1;
			}
			return ce1.getSource() < ce2.getSource() ? -1 : 1;
		}

	}

}
